package org.example;

import java.util.*;

//public class Main {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int N = scanner.nextInt();
//        int M = scanner.nextInt();
//        int[][] graph = new int[N + 1][N + 1];
//        for (int i = 0; i < M; i++) {
//            int u = scanner.nextInt();
//            int v = scanner.nextInt();
//            int w = scanner.nextInt();
//            graph[u][v] = w;
////            graph[v][u] = w;
//        }
//
//        boolean[] visited = new boolean[N + 1];
//        int[] minDist = new int[N + 1];
//        for (int i = 1; i <= N; i++) {
//            minDist[i] = Integer.MAX_VALUE;
//        }
//        minDist[1] = 0;
//
//        for (int i = 1; i <= N; i++) {
//            //获取下一个要访问的节点
//            int cur = -1;
//            for (int j = 1; j <= N; j++) {
//                if (!visited[j] && minDist[j] < Integer.MAX_VALUE) {
//                    if (cur == -1 || minDist[cur] > minDist[j]) {
//                        cur = j;
//                    }
//                }
//            }
//            if (cur == -1) {
//                break;
//            }
//            visited[cur] = true;
//
//            //以当前访问节点更新cost数组
//            for (int j = 1; j <= N; j++) {
//                if (!visited[j] && graph[cur][j] > 0 && minDist[cur] + graph[cur][j] < minDist[j]) {
//                    minDist[j] = minDist[cur] + graph[cur][j];
////                    path[j] = cur;
//                }
//            }
//        }
//        if (minDist[N] < Integer.MAX_VALUE) {
//            System.out.println(minDist[N]);
//        } else {
//            System.out.println(-1);
//        }
//    }
//}


class Edge {
    public final int to;
    public final int cost;
    public Edge(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}

class Pair {
    public final int first;
    public final int second;
    public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

class MyComparator implements Comparator<Pair> {
    @Override
    public int compare(Pair p1, Pair p2) {
        return Integer.compare(p1.second, p2.second);
    }
}

//堆优化版
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        List<List<Edge>> graph = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < M; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            graph.get(u).add(new Edge(v, w));
        }

        boolean[] visited = new boolean[N + 1];
        int[] minDist = new int[N + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[1] = 0;

        PriorityQueue<Pair> queue = new PriorityQueue<>(new MyComparator());
        queue.offer(new Pair(1, 0));        //放入第一个节点

        while (!queue.isEmpty()) {
            Pair cur = queue.poll();
            int curIdx = cur.first;
            int curMinDist = cur.second;
            if (visited[curIdx]) {
                continue;
            }

            visited[curIdx] = true;

            for (Edge edge : graph.get(curIdx)) {
                if (!visited[edge.to] && curMinDist + edge.cost < minDist[edge.to]) {
                    minDist[edge.to] = curMinDist + edge.cost;
                    queue.offer(new Pair(edge.to, minDist[edge.to]));
                }
            }
        }

        if (minDist[N] < Integer.MAX_VALUE) {
            System.out.println(minDist[N]);
        } else {
            System.out.println(-1);
        }
    }
}